// https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/

// 算法思路总结：
// 1. 广度优先搜索实现二叉树的锯齿形层序遍历
// 2. 先进行标准层序遍历，记录每层节点值
// 3. 遍历完成后，将奇数层（从0开始）的结果反转
// 4. 偶数层从左到右，奇数层从右到左
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <queue>
#include <vector>
#include <algorithm>

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

TreeNode* buildTree(const vector<string>& nodes) 
{
    if (nodes.empty() || nodes[0] == "null") return nullptr;
    
    TreeNode* root = new TreeNode(stoi(nodes[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    
    while (!q.empty() && i < nodes.size()) 
    {
        TreeNode* current = q.front();
        q.pop();
        
        if (i < nodes.size() && nodes[i] != "null") 
        {
            current->left = new TreeNode(stoi(nodes[i]));
            q.push(current->left);
        }
        i++;
        
        if (i < nodes.size() && nodes[i] != "null") 
        {
            current->right = new TreeNode(stoi(nodes[i]));
            q.push(current->right);
        }
        i++;
    }
    
    return root;
}

void printResult(const vector<vector<int>>& result) 
{
    cout << "[";
    for (int i = 0; i < result.size(); ++i) 
    {
        cout << "[";
        for (int j = 0; j < result[i].size(); ++j) 
        {
            cout << result[i][j];
            if (j < result[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i < result.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

class Solution 
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    {
        if (root == nullptr) return {};

        queue<TreeNode*> q;
        q.push(root);
        vector<vector<int>> ret;

        while (!q.empty())
        {
            int sz = q.size();
            vector<int> tmp;
            for (int i = 0 ; i < sz ; i++)
            {
                TreeNode* front = q.front();
                q.pop();
                tmp.push_back(front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            ret.push_back(move(tmp));
        }

        for (int i = 0 ; i < ret.size() ; i++)
            if (i & 1) reverse(ret[i].begin(), ret[i].end());

        return ret;
    }
};

int main()
{
    vector<string> nodes1 = {"3", "9", "20", "null", "null", "15", "7"};
    vector<string> nodes2 = {"1"};

    Solution sol;

    auto root1 = buildTree(nodes1);
    auto root2 = buildTree(nodes2);

    vector<vector<int>> result1 = sol.zigzagLevelOrder(root1);
    vector<vector<int>> result2 = sol.zigzagLevelOrder(root2);

    printResult(result1);
    printResult(result2);

    return 0;
}